package 动态规划.样本对应模型;
/**
 * https://zhuanlan.zhihu.com/p/411052401
 * 有关子序列 的相关题目
 *
 * 先对这个 思路 做一个 说明 :
 * 我写的 这种
 *
 *
 *
 *
 */
public class 最长公共子序列 {

	/*
	 这里 进行一下 更正， f（i， j ） 表示的是：  s1 在 i ~ len1 - 1 **区间内** 与 s2 在  j ~ len2 - 1 区间范围内 ：
	 最长公共子序列的 长度！
	 f（） 函数的 含义 ，要十分的清楚
	 */

	public static int process(int i,int j,char []s1 ,char[] s2) {
		if(i == s1.length || j == s2.length)
			return 0;
		int r1,r2,r3;
		r1 = r2  =r3 = 0;
		if(s1[i] == s2[j]) {
			 r1 = process(i + 1,j + 1,s1,s2) + 1;
		}
		else {
			 r2 = process(i + 1,j,s1,s2);
			 r3 = process(i,j + 1,s1,s2);
		}
		return Math.max(r1,Math.max(r2, r3));
	}
	
	public static void main(String []args) {
//		String s1 = "a1000fdqqq2";
//		String s2 = "12d00ea3fdqqq2";
		String s1 = "1135";
		String s2 = "135";
		System.out.println(process(0,0,s1.toCharArray(),s2.toCharArray()));
		System.out.println(dp(s1,s2));
		System.out.println(recursion(s1.toCharArray(),s2.toCharArray(),0,0));
	}
	
	
	
	public static int dp(String s1,String s2) {
		int len1 = s1.length();
		int len2 = s2.length();
		char [] str1 = s1.toCharArray();
		char [] str2 = s2.toCharArray();
		int dp [][] = new int [len1 + 1][len2 + 1];
		for(int i = len1 - 1 ;i >= 0; i--) {
			for(int j = len2 -1; j >= 0;j --) {
				if(str1[i] == str2[j])
					dp[i][j] = dp[i + 1][j + 1] + 1;
				else {
					dp[i][j] = Math.max(dp[i][j], dp[i+ 1][j]);
					dp[i][j] = Math.max(dp[i][j], dp[i][j + 1]);
				}
				
			}
		}
		return dp[0][0];
	}
	
	
	
	
	
	
	
	
	
	/**
	 * 注意 i，j 表示的含义：
	 * i，j 表示 s1 以 i 开头， 和 s2  以  j 开头 ，的最长公共子序列的长度，
	 * 递归   返回 的 值 的含义 和  dp[i][j]  值的  含义都是这个 意义!
	 */
	
	public static int recursion(char []s1 ,char  s2[] ,int i,int j) {
		if(i == s1.length || j == s2.length)
			return 0;
//		int ans1,ans2,ans3;
//		ans1 = ans2 = ans3  = 0;
//		if(s1[i] == s2[j])
//			ans1 = recursion(s1,s2,i + 1,j + 1) + 1;
//		// 这里 不写 else 结果是没有错的  但是 多 计算了 一些 没用的 东西！
//		ans2 = recursion(s1,s2,i + 1,j);
//		ans3 = recursion(s1,s2,i,j + 1);
//		return Math.max(ans1, Math.max(ans2, ans3));
		// 这写的不骚 ？

 		return Math.max(s1[i] == s2[j] ? recursion(s1,s2,i + 1,j + 1) + 1: 
 			Math.max(recursion(s1,s2,i + 1,j), recursion(s1,s2,i,j + 1)), 0);
	}
	
	
	
	
	
	
	
}
